基于子抽样方法对大规模数据集进行特征筛选
董灿，复旦大学大数据学院应用统计专业2023级硕士生。
今天要和大家分享Xuening Zhu & Rui Pan & Shuyuan Wu & Hansheng Wang, 2022. Feature Screening for Massive Data Analysis by Subsampling, https://doi.org/10.1080/07350015.2021.1990771，该文章于2022年发表在 Journal of Business & Economic Statistics上。
介绍
现代统计分析经常面临着具有大量特征的海量数据集。海量的数据大小和高维度的特征给数据存储、通信和统计分析带来了挑战。一方面，大量的数据使得数据存储和计算变得困难。因此，提出了子抽样方法(Ma, Mahoney, and Yu 2015; Wang, Zhu, and Ma 2018; Wang, Yang, and Stufken 2019; Yu et al. 2020)和分布式统计工具(Shamir, Srebro, and Zhang 2014; Chang, Lin, and Wang 2017; Jordan, Lee, and Yang 2019; Fan et al. 2019) ，并对其相应的理论特性进行了广泛研究。另一方面，从各个学科的数据中可能获得成千上万个特征，这使得高维分析的问题变得重要。特征筛选方法的提出和广泛应用使统计分析（例如回归分析）变得可行。
在过去的十年中，由于大规模数据集的出现，学术界提出了各种子抽样方法。一方面，子抽样使得对大规模数据集的计算变得可行；另一方面，它解决了自动统计推断的问题，例如估计样本相关性的标准误差。尽管现有的子抽样方法可以实现自动统计推断，但它们通常是针对具有固定维度的数据而设计的方法。当特征具有高维度时，一种自然的策略是筛选出不相关的特征，以便进一步的分析。特征筛选方法的文献非常丰富，包括基于Pearson相关性的确保独立筛选（SIS）方法、基于距离相关性的无模型确保独立筛选（DC-SIS）方法等，最近的研究还涉及基于逐分量去偏的分布式特征筛选方法，该方法适用于海量数据集，并依赖于分布式结构。
该文章主要针对具有超高维特征的大规模数据集，提出了基于子采样方法的特征筛选。该方法通过对大规模数据集进行重复子抽样来实现，可以运用于具有内存限制的分析场景。为了进行这一过程，该文首先基于子样本计算了R方筛选度量（以及相关的样本矩）。其次，考虑了三种方法合并局部统计量信息：1、简单的平均方法；2、Jackknife去偏筛选度量（ jackknife debiased screening measure）；3、聚合矩筛选度量（aggregated moment screening measure）。其中，后两种方法都能减少子抽样筛选度量的偏差，从而提高特征筛选的准确性。最后，该文章考虑了一种新颖的顺序抽样方法（SAS, Sequential Addressing Subsampling)，它在计算效率上比传统的随机抽样方法更高。该文章还严格讨论了这三种筛选度量在两种抽样方法（即随机抽样方法和顺序寻址子抽样方法）下的理论特性。最后，作者通过一个包含3270万条记录的航空数据集展示了所提出方法的实用性。
模型设定和子抽样方法
首先，介绍该文章模型的设定、子抽样方法以及通过子抽样方法的特征筛选度量。
2.1 模型和标注
假设有个观测值，标记为 。对于第 个观测值，将其记录为连续响应变量以及相关的协变量向量。考虑协变量维度 非常高的情况。具体而言，将 根据变量类型进行划分，即, 其中 代表定量变量， 代表定性变量，有 。假设第 个定性变量 有 个水平，将其转化为 个虚拟变量表示，形式如下： ,，在不失一般性的情况下，为基准水平。为了对连续型响应变量建模，考虑线性回归模型：
记 以及 。 的第 列向量记为 。在高维情况下，通常假设稀疏性，即只有一组重要的特征对响应变量产生显著影响。定义 为定量变量的真实模型。对于定性变量，如果存在至少一个水平 满足，则 记为重要。等价地，定性变量的真实模型定义为 存在使得。
2.2 顺序寻址子抽样（SAS, Sequential Addressing Subsampling)
接下来介绍该文章采用的两种重复子抽样方法：随机寻址抽样（RAS）以及顺序寻址子抽样（SAS）。
在大规模数据集中，样本量非常大。因此，在整个数据集上进行统计分析是非常耗时的，甚至有时在内存的限制下是不可行的。作为一种替代方案，可以进行重复的子抽样，并基于子样本进行统计分析。
一种直接的方法是从原始数据集中进行有放回的重复抽样。这种方案被称为随机寻址抽样（Random Addressing Sampling，RAS），它需要通过对硬盘上的指针进行次寻址来进行个观测值的抽样。在整个数据无法一次性读入内存时，直接从硬盘上进行抽样十分有效。然而，对于大规模数据集来说，RAS过程非常耗时。
为了解决这个问题，Pan等人（2020）提出了一种顺序寻址子抽样（Sequential Addressing Subsampling，SAS）的方法，该方法首先通过随机排列所有数据点来对数据集进行洗牌过程。洗牌过程只进行一次。接着，在硬盘上随机寻址一个数据点，并将后续的个数据点一次性读入内存。该过程产生一个顺序子样本。需要注意的是，SAS方法只需要一次硬盘寻址就可以获得一个顺序子样本，从而大大降低了抽样成本。
需要注意的是，与传统抽样方法相比，SAS方法的抽样空间更小。具体而言，对于SAS方法，在数据洗牌的情况下，只能生成个子样本。相比之下，对于传统的抽样方法，子样本有种可能的组合，这个数量要大得多。因此，需要仔细选择子样本大小和重复子样本的数量，以使该过程有效运行。
另外，顺序寻址方法的思想也可以应用于分而治之类型的方法中。具体而言，在数据洗牌之后，可以将整个数据集分割成个非重叠的可管理的片段，每个片段的大小为。因此，可以基于每个片段计算相关统计量。作者将这种方法称为分而治之（DC）方法。该方法与SAS方法具有相同的思想，但不需要子抽样过程。与RAS和SAS类型的抽样方法相比，DC方法的段数要小得多，特别是当较大时。在该文章理论分析部分提出这可能导致较差的统计推断性能。
2.3 通过子抽样方法的特征筛选度量
通过子抽样进行特征筛选的一种直接方法是使用每个子抽样数据计算筛选度量，然后通过简单平均方法将它们合并。将通过这个过程得出的筛选度量称为简单平均筛选度量。尽管简单平均筛选度量容易获取，但它产生了相当大的偏差。为了纠正偏差问题，该文章提出了两种基于 方设计筛选度量。
第一种筛选度量称为去偏平均筛选（DAS）度量，即在子抽样度量的简单平均基础上，额外进行了刀切法去偏。第二种方法称为聚合矩筛选（AMS）度量，它首先基于子抽样计算样本矩，然后将它们重新组合在一起形成最终结果。上述两种筛选度量的基本思想如下图所示。
接下来详细说明筛选度量的细节。首先描述基于一个子抽样的方筛选度量。假设进行了次抽样过程，将与第个子抽样相关联的预测变量和响应变量表示为：
方便起见，对 和 进行缩放使得 和。设感兴趣的定量变量集合为 。对第 个子抽样，令 : 。相应地，定义 。以 作为协变量， 作为响应变量， 则第个子抽样的方可以表示为：
上述筛选度量可以看作是单变量情况的扩展。通常情况下，对于一个定量变量，我们有M。在这种情况下，回归方等同于 和 之间的相关系数的平方。因此，上述筛选度量与Fan和Lv（2008）提出的SIS（Sure Independence Screening）方法相同。对于一个具有个水平的定性变量，每个水平的信号强度可能太弱，无法通过SIS方法检测出来。因此，将这样的变量作为一个整体进行评估更为合理。
同时，该提出的框架具有很大的扩展潜力。特别是，实践者可以考虑针对不同的变量组使用不同的筛选度量。例如，可以考虑使用基于方的度量来处理定量变量，并使用距离相关性（Li, Zhong, and Zhu 2012b）来处理定性变量。在这种情况下，可以灵活调整方程的定义来筛选不同的变量组。方筛选度量也可以轻松扩展到条件独立性筛选（Fan and Lv 2008）、成对交互作用筛选（Fan et al. 2016；Zhou et al. 2019）和其他许多应用场景。最后，该框架也很容易扩展到广义线性模型。在这种情况下，可以修正方筛选度量以适应广义数据类型。具体来说，可以使用基于似然的筛选度量（Fan et al. 2010）、距离相关性（Li, Zhong, and Zhu 2012b）和无模型独立性筛选方法（Zhou, Zhu, and Li 2020）来处理这种情况。
给定筛选度量，特征筛选的步骤如下：
对于一个定量变量 , 令 ，只用第个子抽样时，记 ;
对于给定的常数 ，通过 估计 。
类似地，对于一个定性变量 , 记 为边际 方，并通过估计 ，其中是预先指定的常数。
以下详细讨论了提出的三种筛选度量。
2.3.1 简单平均筛选（AVS, simple Average Screening )
基于方筛选度量，通过对所有子抽样进行简单平均定义简单平均筛选（AVS）度量：
这一思想在文献中被广泛应用（Kleiner等，2014年；Sengupta, Volgushev和Shao，2016年），并且足够灵活，可以扩展到其他筛选度量。然而，该文章理论分析部分推导出这种方法会产生阶的偏差。只要子抽样大小很大或者重要特征的信号强度很强，这种偏差是可以忽略的。然而，增加子抽样大小需要更多次地访问硬盘，这会消耗时间。为了减轻偏差问题，同时保持紧凑的子抽样大小，接下来对简单平均筛选度量进行了调整以减少偏差。
2.3.2 去偏平均筛选（DAS, Debiased Average Screening）
首先介绍Jackknife去偏平均筛选度量。将表示为第个子抽样中剔除第个样本后的数据，将 表示为第 个子抽样中剔除第个样本后的响应变量。相应地，定义 ，，以及 。那么留一法的方估计量可以表示为：
偏差估计为 。这就得到了Jackknife去偏简单平均筛选度量（DAS），定义如下：
上述DAS度量的偏差从AVS度量的 大幅降低至 。因此，这种方法可以使用较小的子抽样大小，并确保高精度。
2.3.3 聚合矩筛选（AMS，Aggregated Moment Screening）
DAS度量容易通过相同的Jackknife偏差减少的过程来扩展到其他筛选度量；因此，它具有灵活性。除了这种方法，注意到方程：
类似地，对于中的一组定性变量，可以以相同的方式定义 以及 。AMS度量具有较小的偏差，并且可以视为一种分量化的去偏方法（Li等，2020）。当超高维线性回归模型的预测变量之间存在较高的相关性水平时，该文建议使用迭代筛选策略（Fan和Lv，2008；Cho和Fryzlewicz，2012）。其基本思想是通过迭代地应用特征筛选和变量选择过程来增强方法效能。
进一步地，该文分别从上述三种筛选度量在RAS（随机寻址抽样）以及SAS（顺序寻址子抽样）的收敛性质、在RAS（随机寻址抽样）和DC（分而治之）下的统计推断性质以及筛选一致性，讨论并严格推导了该文章提出的在各种子抽样方案下均匀收敛和筛选一致性的理论性质，并在附录中进行了严格证明。
实例
该文章使用美国航空数据集来说明所提出的方法。所使用的数据集可在美国统计协会的官方网站上获取（http://stat-computing.org/dataexpo/2009）。航空数据集包含了1987年至2008年间美国商业航班的信息。经过基本的数据清洗，作者保留了2004年至2008年间的航班信息，共有12个变量。这些变量包括：ArrTime（实际到达时间）、Year（年份）、Month（月份）、DayofMonth（日期）、DayofWeek（星期几）、CRSElapsedTime（计划飞行时间）、CRSArrTime（计划到达时间）、ActualElapsedTime（实际飞行时间）、Distance（飞行距离）、UniqueCarrier（航空公司）、Dest（目的地）和Origin（出发地）。具体的变量信息见下图：
在分析中，作者将ArrTime作为响应变量，并从其他变量生成相应的协变量。首先，根据州将Origin中的城市进行划分。接下来，保留前10个州的城市，并将其他州的城市归为一个州。接着，对于每个州，保留前2个城市，并将其他城市归为一个城市。通过这个过程，变量Origin生成了10个分类变量。类似的过程也适用于变量Dest。最后，生成响应变量ArriveTime和预测变量ActualElapsedTime的1到40个滞后值，以检测滞后效应。最终，得到了109个预测变量。所有的数值变量都进行了标准化，均值为0，方差为1，对应着条记录，数据集的大小为27.6 GB。
为了评估筛选的准确性，使用整个数据集的方筛选度量作为基准，对比三个筛选度量（AVS、DAS和AMS）。由于在实际数据分析中不知道真相（即 和 ），因此对AUC度量进行了修订，具体如下（以AVS度量为例）：
另外， 以AVS为例， ， ， 其中 ， ，该数据集的具体结果如下表。
从表中可以看出，在所有设置中，RAS和SAS的性能相当，但是SAS的时间成本约为RAS的1/8。其次，当或增加时，SE减小，而Bias只有在增加时才减小。在比较三个度量时，AMS具有最小的SE和Bias。此外，DAS和AMS度量的Bias要明显小于AVS度量的Bias。
在筛选准确性方面，AMS和DAS度量的AUC值比AVS度量高，其中AMS具有最大的AUC值。例如，在B = 500，n = 50（在SAS下）的情况下，AMS度量的AUC为90.91％，大于DAS（89.44％）和AVS（88.16％）方法的AUC。
讨论
该文章基于子样本开发了两种用于超高维大数据集的特征筛选方法。主要贡献如下：
1、能够直接在硬盘上进行采样，大大降低了时间成本，并使得在内存受限的情况下进行子抽样成为可能。这对于大规模数据集非常有用。
2、该文提出特征筛选度量可以处理具有不同水平数量的定性特征，其余文献中尚未对这种情况进行充分研究，但在实践中经常遇到。
3、该文在各种子抽样方案下推导了均匀收敛和筛选一致性的理论性质。
另外，根据理论和实证研究，DAS度量和AMS度量在减小偏差方面显示出优势。在实践中，特征筛选方法的准确性是可比较的，并且顺序寻址子采样方法在计算效率上更高。
在文章的结尾，作者提供了几个未来研究的主题。首先，可以将其他著名的特征筛选方法，如向前筛选度量（Wang 2009）、RRCS（Li等，2012a）和DC-SIS（Li、Zhong和Zhu，2012b）纳入该文的子采样方法中。其次，在高维建模领域，变量选择是另一个重要的主题，应该设计和研究用于变量选择的子采样方法。最后，所提出的子采样方法不能应用于相关数据（例如，时间序列和空间数据）。因此，需要探究一种保持数据依赖结构并具有低计算成本的子采样方法。
参考文献
Barut, E., Fan, J., and Verhasselt, A. (2016), “Conditional Sure Independence Screening,” Journal of the American Statistical Association, 111, 1266–1277. Chang, X., Lin, S.-B., and Wang, Y. (2017), “Divide and Conquer Local Average Regression,” Electronic Journal of Statistics, 11, 1326–1350. Cho, H. and Fryzlewicz, P. (2012), “High Dimensional Variable Selection via Tilting,” Journal of the Royal Statistical Society, Series B, 74, 593–622. Elith, J., Graham, C. H., Anderson, R. P., Dudík, M., Ferrier, S., Guisan, A., Hijmans, R. J., Huettmann, F., Leathwick, J. R., Lehmann, A., et al. (2006), “Novel Methods Improve Prediction of Species Distributions from Occurrence Data,” Ecography, 29, 129–151. Fan, J., Feng, Y., and Song, R. (2011), “Nonparametric Independence Screening in Sparse Ultra-High-Dimensional Additive Models,” Journal of the American Statistical Association, 106, 544–557. Fan, J., Li, R., Zhang, C.-H., and Zou, H. (2020), Statistical Foundations of Data Science, Boca Raton, FL: CRC press. Fan, J. and Lv, J. (2008), “Sure Independence Screening for Ultra-High Dimensional Feature Space” (with discussion), Journal of the Royal Statistical Society, Series B, 70, 849–911. Fan, J., Song, R., et al. (2010), “Sure Independence Screening in Generalized Linear Models with NP-Dimensionality,” The Annals of Statistics, 38, 3567–3604. Fan, J., Wang, D., Wang, K., and Zhu, Z. (2019), “Distributed Estimation of Principal Eigenspaces,” Annals of Statistics, 47, 3009. Fan, Y., Kong, Y., Li, D., and Lv, J. (2016), “Interaction Pursuit With Feature Screening and Selection,” arXiv:1605.08933. Hanley, J. A., and McNeil, B. J. (1982), “The Meaning and Use of the Area Under a Receiver Operating Characteristic (ROC) Curve,” Radiology, 143, 29–36. Herlocker, J. L., Konstan, J. A., Terveen, L. G., and Riedl, J. T. (2004), “Evaluating Collaborative Filtering Recommender Systems,” ACM Transactions on Information Systems (TOIS), 22, 5–53. Jordan, M. I., Lee, J. D., and Yang, Y. (2019), “Communication-Efficient Distributed Statistical Inference,” Journal of the American Statistical Association, 526, 668–681. Kleiner, A., Talwalkar, A., Sarkar, P., and Jordan, M. I. (2014), “A Scalable Bootstrap for Massive Data,” Journal of the Royal Statistical Society, Series B, 76, 795–816. Li, G., Peng, H., Zhang, J., Zhu, L., et al. (2012a), “Robust Rank Correlation Based Screening,” The Annals of Statistics, 40, 1846–1877. Li, R., Zhong, W., and Zhu, L. (2012b), “Feature Screening via Distance Correlation Learning,” Journal of the American Statistical Association, 107, 1129–1139. Li, X., Li, R., Xia, Z., and Xu, C. (2020), “Distributed Feature Screening via Componentwise Debiasing.” Journal of Machine Learning Research, 21, 1–32. Ma, P., Mahoney, M. W., and Yu, B. (2015), “A Statistical Perspective on Algorithmic Leveraging,” The Journal of Machine Learning Research, 16, 861–911. McKinney, S. M., Sieniek, M., Godbole, V., Godwin, J., Antropova, N., Ashrafian, H., Back, T., Chesus, M., Corrado, G. S., Darzi, A., et al. (2020), “International Evaluation of an AI System for Breast Cancer Screening,” Nature, 577, 89–94. Pan, R., Wang, H., and Li, R. (2016), “Ultrahigh-Dimensional Multiclass Linear Discriminant Analysis by Pairwise sure Independence Screening,” Journal of the American Statistical Association, 111, 169–179. Pan, R., Zhu, Y., Guo, B., Zhu, X., and Wang, H. (2020), “A Sequential Addressing Subsampling Method for Massive Data Analysis With Memory Constraint,” Working Paper. Sengupta, S., Volgushev, S., and Shao, X. (2016), “A Subsampled Double Bootstrap for Massive Data,” Journal of the American Statistical Association, 111, 1222–1232. Shamir, O., Srebro, N., and Zhang, T. (2014), “Communication-Efficient Distributed Optimization Using an Approximate Newton-Type Method,” in International Conference on Machine Learning, pp. 1000–1008. Wang, H. (2009), “Forward Regression for Ultra-High Dimensional Variable Screening,” Journal of the American Statistical Association, 104, 1512–1524. Wang, H. (2012), “Factor Profiled Sure Independence Screening,” Biometrika, 99, 15–28. Wang, H. (2019), “More Efficient Estimation for Logistic Regression with Optimal Subsamples,” Journal of Machine Learning Research, 20, 1–59. Wang, H., Yang, M., and Stufken, J. (2019), “Information-Based Optimal Subdata Selection for Big Data Linear Regression,” Journal of the American Statistical Association, 114, 393–405. Wang, H., Zhu, R., and Ma, P. (2018), “Optimal Subsampling for Large Sample Logistic Regression,” Journal of the American Statistical Association, 113, 829–844. Wang, L., Kim, Y., and Li, R. (2013), “Calibrating Non-Convex Penalized Regression in Ultra-High Dimension,” Annals of Statistics, 41, 2505. Wu, Y. and Yin, G. (2015), “Conditional Quantile Screening in Ultrahigh-Dimensional Heterogeneous Data,” Biometrika, 102, 65–76. Yu, J., Wang, H., Ai, M., and Zhang, H. (2020), “Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators with Massive Data,” Journal of the American Statistical Association, 1–29, DOI: 10.1080/01621459.2020.1773832. Zhou, M., Dai, M., Yao, Y., Liu, J., Yang, C., and Peng, H. (2019), “BOLT-SSI: A Statistical Approach to Screening Interaction Effects for Ultra-High Dimensional Data,” arXiv:1902.03525. Zhou, T., Zhu, L., and Li, R. (2020), “Model-Free Forward Regression via Cumulative Divergence,” Journal of the American Statistical Association, 531, 1393–1405.